package com.二叉树2;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
    public Node(Integer[] nums){
        Node cur = this;
        cur.next = new Node(nums[0]);
       Queue<Node> queue = new LinkedList<>();
        queue.add(cur.next);
        for(int i = 1;i<nums.length;i++){
            Node tmp = queue.poll();
            Node left = new Node(nums[i]);
            tmp.left = left;
            ++i;
            if(i>=nums.length){
                break;
            }
            Node right = new Node(nums[i]);
            tmp.right = right;
            queue.add(left);
            queue.add(right);


        }
    }

};

/**
 * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 填充节点的下一个节点右侧节点指针 {
    static class Solution{
        public Node connect2(Node root){
            Queue<Node> q=new LinkedList<>();
            if(root==null)
                return null;
            q.add(root);
            while(!q.isEmpty()){
                int size=q.size();
                for(int i=0;i<size;i++){
                    Node node=q.remove();
                    if(i<size-1)            //节点node不是当前层的最后一个(感谢官方给的提示)
                        node.next=q.peek(); //将node指向队列中的下一个
                    if(node.left!=null)
                        q.add(node.left);
                    if(node.right!=null)
                        q.add(node.right);
                }
            }
            return root;
        }
        public Node connect(Node root){
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size = queue.size();

               for(int i  = 0 ;i<size;i++){
                   Node node = queue.poll();
                   if(i<size-1) {
                       node.next = queue.peek();
                   }
                   if(node.left !=null){
                       queue.add(node.left);
                   }
                   if(node.right != null){
                       queue.add(node.right);
                   }
               }



            }
            return root;

        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            Node connect = solution.connect(new Node(new Integer[]{1,2,3,4,5,6,7}).next);

        }
    }
}
